import java.util.*;
public class Heapsort {

//	private int[] arr;
//	private int length;
//	
//public void buildHeap()
//    {		while(length!=0)
//		{
//			for(int i = (length - 1)/2; i>=0; i--)
//			{
//				maxHeap(i);
//			}
//			exchange(0,length-1);
//			length--;
//		}
//    }
//	private void maxHeap(int parent)
//	{
//		int left=2*parent+1;
//		int right=2*parent+2;
//		int largest=parent;
//		if (left< length && arr[left]>arr[parent])
//		{
//			largest=left;
//		}
//		if (right< length && arr[right]>arr[largest])
//		{
//			largest=right;
//		}
//		if (largest!=parent)
//		{
//			exchange(parent, largest);
//			maxHeap(largest);
//		}
//	}
//	private void exchange(int i, int j)
//	{
//		int tmp=arr[i];
//		arr[i]=arr[j];
//		arr[j]=tmp;
//	}
//	public Heapsort(int length)
//	{                     
//		this.length = length;                   
//		arr = new int[length];
//		for(int i=0; i<length; i++)
//		{
//			arr[i] = (int)(Math.random()*100);
//		}
//		printArray(arr,length); 
//	}
//	private void printArray(int []arr,int lenght) 
//	{
//		System.out.print("[ ");
//		for(int i=0; i<lenght; i++)
//		{
//			System.out.print(arr[i]+ " ");
//		}
//		System.out.println("]");
//	}
//	public void sort()
//	{
//		
//	}
//	public static void main(String[] args) 
//	{
//		Heapsort hs=new Heapsort(10);
//		int length=hs.length;
//		hs.buildHeap();
//		hs.printArray(hs.arr, length);
//	}

	private  int[] arr;
	private  int length;
	//private  int left;
	//private  int right;
	//private  int largest;
	
	public void buildHeap() {
		 	while(length!=0){
		for(int i = (length - 1)/2; i>=0; i--){
			maxHeap(i);}
		//System.out.println();
		//printArray();
		swap(0,length-1);
		length--;
		 		}		
	}
	public void sort (){
	//	while(left!=)		
	}
	private void maxHeap(int parent){
		int left = 2*parent + 1;
		int right= 2*parent + 2;
		int largest = parent;
		if(left < length && arr[left] > arr[parent])
		{
			largest = left;
		}
		if(right < length && arr[right] > arr[largest])
		{
			largest = right;
		}
		if(largest!=parent){
			swap(parent, largest);
			maxHeap(largest);
		}
	}
	
	private void swap(int i, int j) {
		int tmp = arr[i];
		arr[i]=arr[j];
		arr[j] = tmp;
		
	}
	public Heapsort(int length) {
		this.length = length;
		arr = new int[length];
		for (int i=0; i<length; i++ ){
			arr[i] = (int) (Math.random()*30);
		}
		printArray(arr, length );
	}
	private void printArray(int []arr,int length) {
	System.out.print("[");
	for (int i = 0; i< length; i++){
		System.out.print(arr[i] + " ");
	}
	System.out.print("]\n");
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
	Heapsort hs = new Heapsort(10);
	int length=hs.length;
	hs.buildHeap();
	hs.printArray(hs.arr, length);
	
	}
	}


